# layerNode.mod    
# Yu Liu, 01/2006, add constraints for node failure both layer models

# optimize the cost of top layer links on bottom layers, 
# assuming the unit link cost on the bottom layer
#minimize topo_cost: 
#  sum {(i1,i2) in LINKS, (j1,j2) in EDGES} H[i1,i2,j1,j2];

# Interlayer mapping matrix maps top layer links as the paths at bottom layer.
# These paths fulfill the flow conservation (mass balance) constraints
# The following formula assumes the first group of vertices (at bottom layer) are nodes (at top layer).
# the rest vertices are only for the bottom layer, so their net in/out flows are zeroes.
# H {B^l}^T = [ B^T | 0 ] 
#s.t. mass_baH {(i1,i2) in LINKS, n1 in NODES}:
#  sum {(j1,j2) in EDGES} BL[n1,j1,j2] * H[i1,i2,j1,j2]
#      = B[n1,i1,i2];
#s.t. mass_baH2 {(i1,i2) in LINKS, n1 in VERTS diff NODES}:
#  sum {(j1,j2) in EDGES} BL[n1,j1,j2] * H[i1,i2,j1,j2]
#      = 0;

var HF {LINKS, FAILSL} binary default 0;

# This formula assures the single failure of bottom layer will not partition the top layer.
# It is the matrix format of the 
# C H_f < Ce  or  C(e- H_f)>0
# if cut k only contains failed vert f, then this constraint is dropped
s.t. survHF {f in FAILSL, k in POWNODES: k<>2**(f-1) && k<>2**(MaxNode-f)}:
  sum{v1 in CUTS[k], v2 in NODES diff CUTS[k]:(v1,v2) in LINKS}
    (1- HF[v1,v2,f] ) >= 1; 

# Use max link as a large number
s.t. findHF {f in FAILSL, (v1, v2) in LINKS: v1<>f && v2<>f}:
  HF [v1, v2, f]  <= sum {(j1, j2) in EDGES} FL[f, j1, j2]*H[v1,v2, j1,j2];

s.t. findHF2 {f in FAILSL, (v1, v2) in LINKS: v1<>f && v2<>f}:
  HF [v1, v2, f] * MaxEdge >= sum {(j1, j2) in EDGES} FL[f, j1, j2]*H[v1,v2, j1,j2];
   
# added by Korn, H should have the same mapping for both directions
#s.t. symH {(i1,i2) in LINKS, (j1,j2) in EDGES}:
#   H[i2,i1,j2,j1] = H[i1,i2,j1,j2];

# problem to find interlayer mapping matrix H 
# that assures that the top layer is resilient to single link failure at the bottom layer
problem designHF: topo_cost, mass_baH, mass_baH2, survHF, findHF, findHF2, symH,  H, HF;
